<?php


$arr = array(12, 13, 2, 21, 6, 32, 78, 36, 76, 9);
function bubble_sort($arr): array
{


    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        for ($k = 0; $k < $len - $i; $k++) {
            if ($arr[$k] > $arr[$k + 1]) {
                list($arr[$k], $arr[$k + 1]) = array($arr[$k + 1], $arr[$k]);
            }
        }
    }

    return $arr;
}

function select_sort($arr): array
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $p = $i;
        for ($k = $i + 1; $k < $len; $k++) {
            if ($arr[$p] > $arr[$k]) {
                $p = $k;
            }
        }

        if ($p != $i) {
            list($arr[$i], $arr[$p]) = array($arr[$p], $arr[$i]);
        }
    }

    return $arr;
}

function insert_sort($arr): array
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $tmp = $arr[$i];
        for ($k = $i - 1; $k >= 0; $k--) {
            if ($tmp < $arr[$k]) {
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $tmp;
            } else {
                break;
            }
        }
    }

    return $arr;
}

function quick_sort($arr): array
{

    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }


    $left = [];
    $right = [];
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    quick_sort($left);
    quick_sort($right);

    return array_merge($left, [$arr[0]], $right);
}


//var_export(bubble_sort($arr));
//var_export(select_sort($arr));
//var_export(insert_sort($arr));
var_export(quick_sort($arr));